#include <stdio.h>
#include <stdlib.h>

struct point{
  double x,y;
};

struct triangle{
  struct point vertexes[3];
};

#include "stack.h"

//Function sorts vertexes of monotone polygon from a max y coordinate to the min one
//by means of fusion of left and right sets of vertexes. Output is an array
//where output[i] is a number or vertex in array polygon[] in i order
int *GetVertexesOrder(struct point *polygon, int number_of_vertex) {
  int *temp;  
  int i,i1,i2,maxy,miny;

  temp = (int *)malloc(number_of_vertex*sizeof(int));
  
  maxy = 0;
  miny = 0;
  //The block defines vertex with max and min y coordinates :
  for(i=0;i<number_of_vertex;++i) {
    if(polygon[i].y > polygon[maxy].y) maxy = i;
    if(polygon[i].y < polygon[miny].y) miny = i;
  }
  //polygon[maxy] - vertex with max y coordinate, polygon[miny] - with min one

  //Fusion:
  if (maxy < miny) {
    i1 = maxy;
    i2 = maxy+1;

    for(i=0;i<number_of_vertex;++i) {
      if(polygon[i1].y > polygon[i2].y) {
        temp[i] = i1;
        if (i1 != 0) --i1;
          else i1 = number_of_vertex - 1;
      } else {
        temp[i] = i2++;        
        }
    }
  } else {
    i1 = maxy - 1;
    i2 = maxy;

    for(i=0;i<number_of_vertex;++i) {
      if(polygon[i1].y > polygon[i2].y) {
        temp[i] = i1;
      } else {
        temp[i] = i2;
        if(i2 != number_of_vertex - 1) i2++;
          else i1 = 0;
        }
    }
  }
  return temp;
}

int IsAngleMoreThenPi(struct point p1, struct point p2, struct point p3) {
  return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x) > 0 ? 0:1;
}

int AreVertexesAjacent(int v1, int v2, int max_vertex) {
  if(abs(v1-v2) == 1) return 1;
    else if (abs(v1-v2) == max_vertex-1) return 1;
    else return 0;
}  
//Read the documentation to lern the algorithm
//Function probably destruct truct vertex *sorted_vertexes
struct triangle *MonotonePolygonTriangulation(struct point *polygon,
                                              int *vertexes_order,
                                              int number_of_vertex) {
  struct stack *vertixes_stack,*stack_bottom;
  struct triangle *triangles;
  int i,j,triangles_count,temp;

  triangles = (struct triangle *)malloc((number_of_vertex - 2)*sizeof(struct triangle));
  triangles_count = 0;
  vertixes_stack = NULL;
  vertixes_stack = PUSH(vertixes_stack,&vertexes_order[0]);
  stack_bottom  = vertixes_stack;
  vertixes_stack = PUSH(vertixes_stack,&vertexes_order[1]);
  
  for(i=2;i<number_of_vertex;++i) {
    printf("%d\n",vertexes_order[i]);
    //case 1(Read documentation)
    if(AreVertexesAjacent(vertexes_order[i],*vertixes_stack->data,number_of_vertex) != 1 && 
       AreVertexesAjacent(*stack_bottom->data,vertexes_order[i],number_of_vertex) == 1) {
      printf("case1\n");
      temp = *vertixes_stack->data;

      while(vertixes_stack->next != NULL) {        
        triangles[triangles_count].vertexes[0] = polygon[vertexes_order[i]];
        triangles[triangles_count].vertexes[1] = polygon[*vertixes_stack->data];
        vertixes_stack = POP(vertixes_stack);
        printf("%d\n",*vertixes_stack->data);
        //printf("hi\n");
        triangles[triangles_count].vertexes[2] = polygon[*vertixes_stack->data];
        //printf("hi\n");
        triangles_count++;
        if(vertixes_stack->next == NULL) printf("hi\n");
      }
      //printf("hi\n");
      vertixes_stack = POP(vertixes_stack);
      vertixes_stack = PUSH(vertixes_stack,&temp);
      stack_bottom  = vertixes_stack;
      vertixes_stack = PUSH(vertixes_stack,&vertexes_order[i]);
    //case 2
    } else if(AreVertexesAjacent(vertexes_order[i],*vertixes_stack->data,number_of_vertex) == 1 && 
       AreVertexesAjacent(*stack_bottom->data,vertexes_order[i],number_of_vertex) != 1) {
        printf("case2\n");
        while(vertixes_stack->next != NULL && 
              IsAngleMoreThenPi(polygon[vertexes_order[i]],polygon[*vertixes_stack->data],
              polygon[*vertixes_stack->next->data]) == 1) {
          triangles[triangles_count].vertexes[0] = polygon[vertexes_order[i]];
          triangles[triangles_count].vertexes[1] = polygon[*vertixes_stack->data];
          vertixes_stack = POP(vertixes_stack);
          triangles[triangles_count].vertexes[2] = polygon[*vertixes_stack->data];
          triangles_count++;
        }
        vertixes_stack = PUSH(vertixes_stack,&vertexes_order[i]);
    //case 3
    } else {
      printf("case3\n");
    }
  }
  return triangles;
}
  

int main() {
  struct point *polygon;
  int *vertexes_order;
  struct triangle *result_triangulation;
  int i;

  polygon = (struct point *)malloc(4*sizeof(struct point));
  polygon[0].x = 1;
  polygon[0].y = 1;
  polygon[1].x = 0;
  polygon[1].y = 2;
  polygon[2].x = 0;
  polygon[2].y = 0;
  polygon[3].x = 1;
  polygon[3].y = -1;

  vertexes_order = GetVertexesOrder(polygon,4);
  for(i=0;i<4;++i) 
    printf("%d\n",vertexes_order[i]);

  result_triangulation = MonotonePolygonTriangulation(polygon,vertexes_order,4);

  printf("%.2f %.2f %.2f\n",result_triangulation[0].vertexes[0].x,result_triangulation[0].vertexes[1].x,
    result_triangulation[0].vertexes[2].x);

  return 0;
}
